package cn.javadog.algorithm.d1_100;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: yuy
 * @create: 2020-10-29 13:49
 **/
public class Algorithm4 {

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2}, nums2 = new int[]{3,4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        /**
         * 极端情况
         * 1、len 有 0 的
         * 2、长度完全碾压的，即
         */


        /**
         * 取巧
         * 中位数两种情况，可以取 (k + 1) / 2 & k / 2
         */

        /**
         * 效率
         * 1、时间复杂度，2分法，以长度小的一方2分
         *  a、双数组取 len/2，小的往前进 len/4，大的一方后退与小的一方
         */


        // 正常场景


        int len1 = nums1.length;
        int len2 = nums2.length;
        int maxIdx = (len1 + len2) / 2;
        List<Integer> list = new ArrayList(maxIdx+1);

        int sliderIdx2 = 0, sliderIdx1 = 0;
        above: for (; sliderIdx1 < len1; sliderIdx1++) {
            for (; sliderIdx2 < len2; sliderIdx2++) {
                if (list.size() == maxIdx + 1) {
                    break above;
                }
                list.add(Math.min(nums1[sliderIdx1], nums2[sliderIdx2]));
                // 滑动外面的滑块
                if ((nums2[sliderIdx2] > nums1[sliderIdx1] || sliderIdx2 == len2 - 1) && (sliderIdx1 != len1 - 1)) {
                    continue above;
                }
            }
        }

        if ((len1 + len2) % 2 == 0) {
            return (double) (list.get(maxIdx) + list.get(maxIdx-1)) / 2;
        }else {
            return (double) list.get(maxIdx);
        }
    }

}
